package javalab;

import java.util.Arrays;

/**
 * CS3022 - Lab 1: Java Intro This module defines functions for conducting
 * linear and binary search of an array. For each search, the number of
 * comparisons is returned, instead of the array index for the value found.
 * Module also defines a bubble sort function.
 *
 * Program written in Python, to be translated to Java.
 *
 * @author Timothy Riley
 */
public class SearchSort {

	public static Integer linearSearch(Integer[] searchArray, Integer searchValue) {
		Integer idx = 0;

		while (idx < searchArray.length && searchArray[idx] != searchValue) {
			idx += 1;
		}
		if (idx == searchArray.length) { // searchValue not found
			return 0;
		} else { // searchValue found
			return idx + 1; // return no. comparisons
		}
	}

	public static Integer binarySearch(Integer[] searchArray, Integer searchValue) {
		Integer low = 0;
		Integer high = searchArray.length - 1;
		Integer mid = (int) Math.floor((low + high) / 2);
		Integer cnt = 1;

		while (low <= high && searchArray[mid] != searchValue) {
			cnt += 1;
			if (searchArray[mid] < searchValue) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
			mid = (int) Math.floor((low + high) / 2);
		}
		if (low > high) {
			// searchValue not found
			mid = cnt = 0;
		}
		return cnt; // searchValue found, return no. comparisons
	}

	public static Integer[] bubbleSort(Integer[] searchArray) {
		// create a copy of the array for sorting, to leave the input
		// array unchanged
		Integer[] sortArray = Arrays.copyOf(searchArray, searchArray.length);

		Integer bottom = sortArray.length - 1;
		Boolean swapped = true;

		while (swapped) {
			swapped = false;
			for (int idx = 0; idx < bottom; idx++) {
				if (sortArray[idx] > sortArray[idx + 1]) {
					// then swap [idx] and [idx+1] values
					Integer temp = sortArray[idx];
					sortArray[idx] = sortArray[idx + 1];
					sortArray[idx + 1] = temp;
					swapped = true; // a swap was made
				}

			}
			bottom -= 1;
		}
		return sortArray;
	}
}